package com.company.笔试.寻找第K大数;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author 11
 * @Date 2021/6/9 15:16
 * @Version 1.0
 */
public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return find(a,0,n-1,K);


    }

    private int find(int[] a, int low, int high, int K) {
        //快排步骤  1.寻找中间数mid  比mid大的放左边比mid小的放右边

        int mid = findMid(a,0,a.length);
        if (mid+1<K){//k大于中轴位置往右边找 右边更小
            //2.对mid右边小的数快排
            return find(a,mid+1,high,K);
        }else if (mid+1>K){  //k小于中轴位置往左边找， 左边更大
            //3.对mid左边大的数快排
            return find(a,low,mid-1,K);
        }else {//中轴元素正好是第K大的元素
            return a[mid];
        }

    }

    private int findMid(int[] a, int low, int high) {
        //4.找一个基准.将数组首元素作为每一轮比较的基准
        int pivot = a[low];
        while (low<high){
            //5. 从右往左扫描，比基准元素小的话 跳过，直到遇到比基准元素大的元素跳出
            while (low<high&&a[high]<=pivot) --high;
            // 跳出，比基准元素大的放左边low下标中
            a[low]=a[high];
            //6. 从左往右扫描，比基准元素大的话不管，直到遇到比基准元素小的元素跳出
            while ((low<high&&a[low]>pivot)) ++low;
            // 跳出后，比 基准元素小 的放右边high下标中
            a[high]=a[low];
        }
        // 将基准元素放到中间位置
        a[low] = pivot;

        // 返回数组的中轴位置
        return low;

    }
}
